class Solution1 {
    int[] dx={0,0,1,-1};
    int[] dy={1,-1,0,0};
    boolean[][] vis;
    public boolean exist(char[][] board, String word) {
        int m=board.length;
        int n=board[0].length;
        if(m*n<word.length()) return false;
        vis=new boolean[m][n];
        char start=word.charAt(0);


        for(int i=0;i<m;i++)
            for(int j=0;j<n;j++){
                if(board[i][j]==start){
                    vis[i][j]=true;
                    boolean ret=dfs(board,word,i,j,1);

                    if(ret) return true;
                    vis[i][j]=false;
                }

            }

        return false;
    }


    private boolean dfs(char[][] board,String word,int i,int j,int pos){
        if(pos==word.length()) return true;
        int m=board.length;
        int n=board[0].length;
        boolean flg=false;

        for(int k=0;k<4;k++){
            int x=i+dx[k];
            int y=j+dy[k];

            if(x>=0&&x<m&&y>=0&&y<n&&!vis[x][y]&&board[x][y]==word.charAt(pos)){
                vis[x][y]=true;
                flg=dfs(board,word,x,y,pos+1);
                if(flg) return true;
                vis[x][y]=false;
            }



        }

        return false;



    }
}


class Solution {
    int[] dx={0,0,1,-1};
    int[] dy={1,-1,0,0};
    boolean[][] vis;
    public int getMaximumGold(int[][] grid) {
        int m=grid.length;
        int n=grid[0].length;
        vis=new boolean[m][n];

        int ret=0;

        for(int i=0;i<m;i++)
            for(int j=0;j<n;j++){
                if(grid[i][j]!=0){
                    vis[i][j]=true;
                    ret=Math.max(dfs(grid,i,j,grid[i][j]),ret);
                    vis[i][j]=false;

                }

            }

        return ret;



    }


    private int dfs(int[][] grid,int i,int j,int sum){
        int m=grid.length;
        int n=grid[0].length;

        int max=0;

        for(int k=0;k<4;k++){
            int x=dx[k]+i;
            int y=dy[k]+j;
            if(x>=0&&x<m&&y>=0&&y<n&&!vis[x][y]&&grid[x][y]!=0){
                vis[x][y]=true;
                max=Math.max(dfs(grid,x,y,grid[x][y]),max);
                vis[x][y]=false;
            }
        }

        return sum+max;

    }
}